/**
 * Example adapted from book "Purely Functional Data Structures"
 * by Chris Okasaki.
 */ 
  

/** ===========================================================   
 *            Constraints on the extractor's domain 
 *  ===========================================================  
 */  
   
/* domain
	Dom_T = T &
	Dom_E = E
 */
   

/** ===========================================================   
 *                      Class hierarchy
 *  ===========================================================  
 */
   
sealed abstract class Heap { 
  
  /** mege the current heap <code>this</code> with the <code>that</code> 
   *  heap.
   */
  def merge(that: Heap): Heap = (this: Heap) match {
    case E() => that
    case T(_,x: Elem,a1: Heap,b1: Heap) => (that: Heap) match {
      case E() => this
      case T(_,y: Elem,_,_) if x.leq(y) =>
        a1.makeT(x,b1.merge(that))
      case T(_,y: Elem,a2: Heap, b2: Heap) if !x.leq(y) =>
        a2.makeT(y,this.merge(b2))
    }
  }
  
  /** helper function that calculates the rank of a <code>T</code> node
   *  and swaps its children if necessary.
   */ 
  def makeT(x: Elem, that: Heap): Heap = 
    if(this.rankk() >= that.rankk()) {
      T(that.rankk() + 1, x, this, that)
    } else {
      T(this.rankk() + 1, x, that, this)
    }

  /** find the rank of a heap */
  def rankk(): Int = (this: Heap) match {
    case E() => 0
    case T(rank: Int,_,_,_) => rank
  }
  
  /** insert an element in the current heap <code>this</code>*/
  def insert(x: Elem): Heap = this.merge(T(1,x,E(),E()))
  
  /** Find the smallest element of the current heap <code>this</code>. 
   *  Invariant on this data structure entails that the minimum is at the root.
   */ 
  def findMin(t: Heap): Elem = (t: Heap) match {
    case E() => Predef.error(t.toString())
    case T(_,x: Elem,_,_) => x
  }
  
  /** Delete the smallest element of the current heap <code>this</code>.
   *  Invariant on this data structure entails that the minimum is at the root.
   */
  def deleteMin(t: Heap): Heap = (t: Heap) match {
    case E() => Predef.error(t.toString())
    case T(_,_,a: Heap,b: Heap) => a.merge(b)
  }
   
}

class T(val rank: Int, val el: Elem, val left: Heap,val right: Heap) extends Heap
class E extends Heap


class Elem(val value: Int) {
  
  def leq(that: Elem): Boolean =
    /* postcondition this.value <= that.value
     */
    this.value <= that.value
}

/** ===========================================================   
 *                        Extractors          
 *  ===========================================================  
 */

object T {
  def apply(rank: Int, el: Elem, left: Heap, right: Heap): T = 
    new T(rank,el,left,right)
    
  def unapply(t: T): Option[(Int,Elem,Heap,Heap)] =
    Some(Tuple4(t.rank,t.el,t.left,t.right))
}

object E {
  def apply(): E = new E()
  def unapply(l: E): Boolean = true
}


  
object Main {

  def main(args: Array[String]): Unit =
    E().insert(new Elem(3))
       .insert(new Elem(5))
       .insert(new Elem(4))
       .insert(new Elem(7))
       .insert(new Elem(1))
}